//
// Created by Administrator on 2024/11/8.
//

#include <iostream>
#include "arrUtil.h"

using namespace std;

int part(vector<int> &vv,int l, int r)
{
    int cur = vv[l];
    int el = -1;
    for (int i = 0; i <= r ; ++i)
    {
        if (vv[i]<=cur)
        {
            el++;
            swap(vv[el], vv[i]);
        }
    }
    swap(vv[el],vv[l]);
    return el;
}

void quicksort(vector<int> &vv,int l,int r)
{
    if(l<r)
    {
        int m = part(vv,l,r);
        quicksort(vv,l,m-1);
        quicksort(vv,m+1,r);
    }
}

int main()
{
    // 分成小于等于区和大于区 以第一个数为基准
    vector<int> v = {7, 9, 8, 7, 4, 3, 3, 6};
    randVector(v,300);
//    cout<<part(v,0,v.size()-1)<<endl;
    quicksort(v,0,v.size()-1);
//    printVector(v);
    cout<<checkSortVector(v);
    return 0;
}